/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
 * 如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 * @since 2023-09-07 15:51
 */
public class _079单词搜索 {
    public static void main(String[] args) {
//        char[][] board = {
//                {'A', 'B', 'C', 'E'},
//                {'S', 'F', 'C', 'S'},
//                {'A', 'D', 'E', 'E'}
//        };
//        String word = "ABCCED";
        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'E', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word = "ABCESEEEFS";
        System.out.println(new Solution1().exist(board, word));
    }
}
//修改原数组
class Solution2{
    char[][] map;
    String key;
    boolean find = false;
    int[][] dirs = {
            {-1, 0}, {1, 0}, {0, 1}, {0, -1}
    };
    public boolean exist(char[][] board, String word) {
        this.map = board;
        this.key = word;
        int n = board.length, m = board[0].length;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(word.charAt(0) == board[i][j]){
                    dfs(0, i, j);
                    if(find) return true;
                }
            }
        }
        return false;
    }

    private void dfs(int cur, int i, int j){
        if(find) return;
        if(cur >= key.length() - 1){
            find = true;
            return;
        }
        char temp = map[i][j];
        map[i][j] = '0';    //标记访问过
        for(int[] dir : dirs){
            int x = i + dir[0], y = j + dir[1];
            if(x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] == key.charAt(cur + 1)){
                dfs(cur + 1, x, y);
            }
        }
        //回溯
        map[i][j] = temp;
    }
}

//不修改原数组
class Solution1{
    char[][] map;
    String key;
    boolean find = false;
    boolean[][] visted;
    int[][] dirs = {
            {-1, 0}, {1, 0}, {0, 1}, {0, -1}
    };
    public boolean exist(char[][] board, String word) {
        this.map = board;
        this.key = word;
        int n = board.length, m = board[0].length;
        visted = new boolean[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(word.charAt(0) == board[i][j]){
                    dfs(0, i, j);
                    if(find) return true;
                    fillFalse();
                }
            }
        }
        return false;
    }
    private void fillFalse(){
        for(int i = 0; i < visted.length; i++){
            for(int j = 0; j < visted[0].length; j++){
                visted[i][j] = false;
            }
        }
    }

    private void dfs(int cur, int i, int j){
        if(find) return;
        if(cur >= key.length() - 1){
            find = true;
            return;
        }
        visted[i][j] = true;
        for(int[] dir : dirs){
            int x = i + dir[0], y = j + dir[1];
            if(x >= 0 && x < map.length && y >= 0 && y < map[0].length && !visted[x][y] && map[x][y] == key.charAt(cur + 1)){
                dfs(cur + 1, x, y);
            }
        }
        //回溯
        visted[i][j] = false;
    }
}
